#include<iostream>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<utility>
using namespace std;

//1.两数之和
vector<int> twoSum(vector<int>& nums, int target){
    vector<int> ret;
    //建立一个哈希表
    unordered_map<int, int> hash;
    //遍历数组，获取一个值，用目标和减去当前值得到需要要从哈希表中查找的值
    //如果找到返回这两个的下标，如果没有找到就继续下一个
    int tmp = 0;
    for (int i = 0; i < nums.size(); i++){
        tmp = target - nums[i];
        //如果能找到
        if(hash.count(tmp)){
            ret.push_back(hash[tmp]);
            ret.push_back(i);
        }

        //如果没有找到，就将当前值存放到哈希表中
        hash[nums[i]] = i;
    }

    return ret;
}


//面试题.01.02判断是否未字符串重排
bool CheckPermutation(string s1, string s2){
    if(s1.size()!=s2.size()){
        return false;
    }
    //建立一个哈希表，遍历两个字符串，第一个字符串字符在哈希表中对应的个数++，第二个--
    unordered_map<char, int> hash;
    for (int i = 0;i<s1.size();i++){
        hash[s1[i]]++;
        hash[s2[i]]--;
    }

    //遍历哈希表，如果出现字符个数不为零的，说明不是重排
    for(auto ch : s1){
        if(hash[ch]!=0){
            return false;
        }
    }

    return true;
}


//217.存在重复元素
bool containsDuplicate(vector<int>& nums){
    //建立一个set型的哈希表
    unordered_set<int> hash;
    for(auto num : nums){
        pair<unordered_set<int>::iterator, bool> tmp = hash.insert(num);
        if(tmp.second==false){
            return true;
        }
    }
    return false;
}


//存在重复元素2
bool containsNearbyDuplicate(vector<int>& nums, int k){
    //建立一个map类型的哈希表，建立元素和下标的映射
    unordered_map<int, int> hash;
    for (int i = 0; i < nums.size(); i++){
        //判断当前值是否已经存在用count函数统计个数
        if(hash.count(nums[i]&&i-nums[i]<=k)){
            return true;
        }
        //如果不存在，就存放下标
        else{
            hash[nums[i]] = i;
        }
    }

    return false;
}

//字母异位词分组
vector<vector<string>> groupAnagrams(vector<string>& strs){
    unordered_map<string, vector<string>> hash;

    //遍历字符串数组
    for(auto s : strs){
        string tmp = s;
        sort(tmp.begin(), tmp.end());
        hash[tmp].push_back(s);
    }

    vector<vector<string>> ret;
    for(auto& [x,y] : hash){
        ret.push_back(y);
    }

    return ret;
}

int main(){
    vector<int> nums = {1, 2, 3, 1};
    containsNearbyDuplicate(nums, 3);
    return 0;
}